package offer;

public class EX19 {
    public boolean isMatch(String s, String p) {
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n+1][m+1];

        s = " "+s; //让字符从1开始，制造缓冲,反正都是匹配的
        p = " "+p;

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if(j+1<=m && p.charAt(j+1)=='*') continue;
                if(i>0&&p.charAt(j)!='*'){
                    dp[i][j] = dp[i-1][j-1] &&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='.');
                }
                else if(i>0&&p.charAt(j)=='*'){
                    dp[i][j] = dp[i-1][j]&&s.charAt(i)==p.charAt(j-1)||p.charAt(j-1)=='.'||dp[i][j-2];
                }
            }
        }
        return dp[n][m];
    }
}
